Obeleži sve kategorije koje odgovaraju problemu

Модуларна аритметика

Два цела броја $a$ и $b$ су конгруентна по модулу $n$ ако дају исти остатак при дељењу са $n$, односно ако је њихова разлика $a-b$ дељива са $n$.

Извршавање аритметичких операција по модулу $n$ подразумева да се након примене операције одреди остатак при дељењу са бројем $n$. Важе следеће релације: $$\begin{eqnarray*} (a + b)\,\mathrm{mod}\,n &=& (a\,\mathrm{mod}\,n\ +\ b\,\mathrm{mod}\,n)\,\mathrm{mod}\,n\\ (a \cdot b)\,\mathrm{mod}\,n &=& (a\,\mathrm{mod}\,n\ \cdot\ b\,\mathrm{mod}\,n)\,\mathrm{mod}\,n\\ (b - a)\,\mathrm{mod}\,n &=& (b\,\mathrm{mod}\,n - a\,\mathrm{mod}\,n + n)\,\mathrm{mod}\,n \end{eqnarray*}$$

У пракси, ово је корисно у ситуацијама када збир $a+b$ (односно производ $a\cdot b$) може премашити максималну подржану вредност одговарајућег типа података.

Докажимо релацију о производу (она о збиру се доказује још једноставније). Подсетимо се да је $x\,\mathrm{mod}\,y = r$ ако и само ако постоји $q$ такав да је $x = q\cdot y + r$ и ако је $0 \leq r < y$. Претпоставимо da je $a = q_a\cdot n + r_a$ и $b = q_b\cdot n + r_b$ за $0 \leq r_a, r_b < n$. Тада важи да је $a\cdot b = (q_a \cdot n + r_a) \cdot (q_b \cdot n + r_b) = (q_a \cdot q_b \cdot n + q_a \cdot r_b + r_a\cdot q_b)n + r_a\cdot r_b$. Ако важи да је $r_a \cdot r_b = q\cdot n + r$ за $0 \leq r < n$, тада је $a\cdot b = (q_a \cdot q_b \cdot n + q_a \cdot r_b + r_a\cdot q_b + q)n + r$, па је $(a \cdot b)\,\mathrm{mod}\,n = r$. Важи да је $(a\,\mathrm{mod}\,n\ \cdot\ b\ mod\ n)\,\mathrm{mod}\,n = (r_a \cdot r_b)\,\mathrm{mod}\,n = r,$ чиме је тврђење доказано.

Докажимо релацију о разлици. Додавање броја $n$ служи да се избегне дељење негативних бројева. Подсетимо се да је $x\,\mathrm{mod}\,y = r$ ако и само ако постоји $q$ такав да је $x = q\cdot y + r$ и ако је $0 \leq r < y$. Нека је $a = q_a\cdot n + r_a$ и $b = q_b\cdot n + r_b$, za $0 \leq r_a, r_b < n$. Зато је $a\,\mathrm{mod}\,n = r_a$ и $b\,\mathrm{mod}\,n = r_b$. Нека је $r_b - r_a + n = q\cdot n + r$ за неко $0 \leq r < n$. Зато је $(a\,\mathrm{mod}\,n - b\,\mathrm{mod}\,n + n)\,\mathrm{mod}\,n = (r_b - r_a + n)\,\mathrm{mod}\,\ n = r.$ Такође, важи и да је $b-a = (q_b - q_a)\cdot n + (r_b - r_a) = (q_b - q_a - 1)\cdot n + (r_b - r_a + n) = (q_b - q_a - 1 + q)\cdot n + r$, па је и $(b-a)\,\mathrm{mod}\,n = r$, чиме је тврђење доказано.

У наставку ћемо приказати неколико задатака у којима се примењује модуларна аритметика.